package leetcode.editor.cn;

import java.util.HashMap;
import java.util.Map;

public class P464CanIWin {
    public static void main(String[] args) {
        Solution solution = new P464CanIWin().new Solution();
        System.out.println(solution.canIWin(10, 40));

    }

    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        int maxChoosableInteger;
        Map<Integer, Boolean> map = new HashMap<>();
        public boolean canIWin(int maxChoosableInteger, int desiredTotal) {
            this.maxChoosableInteger = maxChoosableInteger;
            return canIWinS(desiredTotal, 0);
        }

        public boolean canIWinS(int desiredTotal, int i) {
            boolean iwin = false;
            if (map.containsKey(desiredTotal)) {
                 return map.get(desiredTotal);
            }
            for (int j = maxChoosableInteger; j >= 1; j--) {
                if (j < desiredTotal) {
                    iwin |= canIWinS(desiredTotal - j, i + 1);
                } else {
                    if (i % 2 == 0) {
                        map.put(desiredTotal, true);
                        iwin |= true;
                    } else {
                        map.put(desiredTotal, false);
                        iwin |= false;
                    }
                    return iwin;
                }

            }
            return iwin;
        }
    }
//leetcode submit region end(Prohibit modification and deletion)

}